class Solution {
public:
    int findWinningPlayer(vector<int>& skills, int k) {
        // 下面是灵神解法，空间复杂度优化为O(1)
        int winCnt = -1;
        int max_i = 0, n = skills.size();
        for(int i = 0; i < n; i++)
        {
            if(skills[i] > skills[max_i])
            {
                // 更新最大值下标
                max_i = i;
                winCnt = 0;
            }
            if(++winCnt == k)
                break;
        }
        return max_i;

        // 下面是自己实现的方法，时间复杂度是O(N)，但是借助了队列，所以空间复杂度是O(N)
        // queue<pair<int, int>> q;

        // int mx = -1, max_i = -1, n = skills.size(), cnt = 0;
        // for(int i = 0; i < n; i++)
        // {
        //     q.push(pair<int, int>(i, skills[i]));
        //     if(skills[i] > mx)
        //     {
        //         mx = skills[i];
        //         max_i = i;
        //     }
        // }
        
        // pair<int, int> prev = q.front();
        // q.pop();
        // while(n--)
        // {
        //     auto after = q.front();
        //     q.pop();
        //     if(cnt == k)
        //         return prev.first;
        //     if(after.second > prev.second)
        //     {
        //         q.push(prev);
        //         prev = after;
        //         cnt = 1;
        //     }
        //     else
        //     {
        //         q.push(after);
        //         cnt++;
        //     }
        // }

        // // 当 k 很大时，只需返回数组中最大的数的下标
        // // 当 k 很大时，只有当最大数跑到最前面，和后面都比他小的数pk，都是赢的
        // return max_i;
    }
};